package test.algorithm.greedy;

import java.util.Arrays;

/**
 * @Projectname: leetCode
 * @Filename: GiveChange
 * @Author: FANSEA
 * @Date:2024/9/10 9:57
 */
public class GiveChange {
    public static void main(String[] args) {
        int[] coins = {5, 2, 1};
        int amount = 16;
        int[] result = giveChange(coins, amount);
        for (int i = 0; i < result.length; i++) {
            System.out.println(coins[i] + ": " + result[i]);
        }
    }

    private static int[] giveChange(int[] coins, int amount) {
//        Arrays.sort(coins);
        int[] result = new int[coins.length];
        for (int i = 0; i < coins.length; i++) {
            result[i] = amount / coins[i];
            amount = amount - result[i] * coins[i];
            if (amount == 0) {
                break;
            }
        }
        return result;
    }
    private static int giveChangeDP(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        Arrays.fill(dp,amount+1);
        int l = coins.length;
        for (int i = 1; i <= amount; i++) {
           for (int j = 0; j < l; j++) {
               if (i >= coins[j])
                   dp[i] = Math.min(dp[i],dp[i - coins[j]] + 1);
           }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}
